#pragma once

///////////////////////////////////////////
/// 单链表数据结构
template <typename E>
struct LNode
{
    E data;
    LNode *next;
};

/// 设置链表类型
// typedef LNode *LinkList; // for C
template <typename E>
using LinkList = LNode<E> *; // for C++11

/// 初始化链表为空 InitList(&L)
template <typename E>
void InitList(LinkList<E> &L)
{
    L = new LNode<E>;
    L->next = nullptr;
}

/// 链表的插入 ListInsert(&L,i,e)
template <typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    //查找第 i -1 个节点位置
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    //若p存在，在其后面插入e
    if (p && j == i - 1)
    {
        //新建一个节点，保存e
        auto s = new LNode<E>;
        s->data = e;
        s->next = p->next;
        p->next = s;
    }
    else
    {
        throw "i 不合法";
    }
}

///链表的删除
template <typename E>
void ListDelet(LinkList<E> &L, int i, E &e)
{
    //查找第 i-1 个节点的位置
    int j = 0;
    auto p = L;
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }

    //若存在，删除第 i 个节点
    if (p && j == i - 1 && p->next)
    {
        //保存删除的第i个节点
        auto q = p->next;
        e = q->data;
        //删除第i个节点
        p->next = q->next;
        delete q;
    }
    else
    {
        throw "i 不合法";
    }
}